// Problem 029: Distinct powers
// Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
// 2^2=4, 2^3=8, 2^4=16, 2^5=32
// 3^2=9, 3^3=27, 3^4=81, 3^5=243
// 4^2=16, 4^3=64, 4^4=256, 4^5=1024
// 5^2=25, 5^3=125, 5^4=625, 5^5=3125
// If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
// 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
// How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

package main

import (
	"fmt"
)

func p029() {
	const IGNORE = 1
	limit := 9801
	var tbl [101][101]int
	for a := 2; a <= 100; a++ {
		for b := 2; b <= 100 && intPow(a, b) <= 100; b++ {
			for k := 2; k <= 100; k++ {
				kb := k * b
				for d1 := 1; d1 < b; d1++ {
					if kb%d1 == 0 {
						d2 := kb / d1
						if a2 := intPow(a, d1); a2 <= 100 {
							if d2 <= 100 {
								tbl[a2][d2] |= IGNORE
							}
						}
					}
				}
			}
		}
	}
	for r := 2; r <= 100; r++ {
		for c := 2; c <= 100; c++ {
			if tbl[r][c]&IGNORE == IGNORE {
				limit--
			}
		}
	}
	fmt.Println("Problem 029:", limit)
}

func intPow(x, y int) int {
	pow := 1
	for i := 0; i < y; i++ {
		pow *= x
	}
	return pow
}
